/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package uns.fit.gis.alg;

import java.util.Random;

/**
 *
 * @author hoannguyenngoc
 */
public class Hamilton {

    /**
     * @param args the command line arguments
     */
    
    public static void main(String[] args) {
        // TODO code application logic here
        Random rand = new Random();
        int[][] matrix = new int[5][5];
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                matrix[i][j] = Math.abs(rand.nextInt()) % 10;
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
        
        int[] permu = searchHamiltonCycle(matrix, 3);
        System.out.println("result");
        hPrintln(permu);
        System.out.println(getLength(matrix, permu, true));
        System.out.println();
        
        permu = searchHamiltonPath(matrix, 3);
        System.out.println("result");
        hPrintln(permu);
        System.out.println(getLength(matrix, permu, false));
        System.out.println();
/*        
        int[] ip = new int[10];
        for (int i = 0; i < ip.length; i++)
            ip[i] = i;
        ip = rotate(ip, 8);
        hPrintln(ip);
        
        ip = transvere(ip);
        hPrintln(ip); */
    }
    
    public static int[] searchHamiltonCycle(int[][] matrix, int startVertex) 
    {
        int[] ip = new int[matrix.length];
        for (int i = 1; i < ip.length; i++)
            ip[i] = i;
        int[] permu = ip;
        hPrintln(permu);
        System.out.println(getLength(matrix, permu, true));
        
        int minLength = getLength(matrix, ip, true);
        int[] minPermu = ip;
        for (int i = 0; i < giaithua(matrix.length - 1) - 1; i++) {
            permu = permutation(i, ip);
            hPrintln(permu);
            System.out.println(getLength(matrix, permu, true));
            int length = getLength(matrix, permu, true);
            if (length < minLength) {
                minLength = length;
                minPermu = permu;
            }
        }
        
        for (int i = 0; i < minPermu.length; i++)
            if (minPermu[i] == startVertex)
                return rotate(minPermu, i);
        return minPermu;
    }
    
    public static int[] searchHamiltonPath(int[][] matrix, int startVertex)  {
        int[] ip = new int[matrix.length];
        for (int i = 1; i < ip.length; i++)
            ip[i] = i;
        int[] permu = swapVertexInPermu(ip, 0, startVertex);
        hPrintln(permu);
        System.out.println(getLength(matrix, permu, false));
        
        int minLength = getLength(matrix, permu, false);
        int[] minPermu = permu;
        for (int i = 0; i < giaithua(matrix.length - 1) - 1; i++) {
            permu = swapVertexInPermu(permutation(i, ip), 0, startVertex);
            hPrintln(permu);
            System.out.println(getLength(matrix, permu, false));
            int length = getLength(matrix, permu, false);
            if (length < minLength) {
                minLength = length;
                minPermu = permu;
            }
        }
        
        return minPermu;
    }
    
    private static int giaithua(int x) {
        if (x <= 1)
            return 1;
        else
            return x * giaithua(x - 1);
    }
    
    private static int[] permutation(int k, int[] ip) {
        int[] s = cloneIntArray(ip);
        for (int i = 2; i < s.length; i++) {
            int temp = s[i];
            s[i] = s[(k % i) + 1];
            s[(k % i) + 1] = temp;
            k = k / i;
        }
        return s;
    }
    
    private static int[] cloneIntArray(int[] array) {
    	int[] ret = new int[array.length];
    	for(int i = 0; i < array.length; i ++) {
    		ret[i] = array[i];
    	}
    	return ret;
    }
    
    private static int[] swapVertexInPermu(int[] permu, int v1, int v2) {
        if (v1 == v2)
            return permu;
        int[] result = new int[permu.length];
        for (int i = 0; i < permu.length; i++)
            if (permu[i] == v1)
                result[i] = v2;
            else if (permu[i] == v2)
                result[i] = v1;
            else
                result[i] = permu[i];
        return result;
    }
    
    private static void hPrintln(int[] permu) {
        for (int i = 0; i < permu.length; i++)
            System.out.print(permu[i] + " ");
        System.out.print("\t\t\t");
    }
    
    private static int getLength(int[][] matrix, int[] permu, boolean isCycle) {
        int length = 0;
        for (int i = 0; i < permu.length - 1; i++)
            length += matrix[permu[i]][permu[i+1]];
        if (isCycle)
            length += matrix[permu[permu.length - 1]][permu[0]];
        return length;
    }
    
    private static int[] rotate(int[] permu, int vIndex) {
        int[] result = new int[permu.length];
        for (int i = 0; i < permu.length; i++)
            if (i >= vIndex)
                result[i - vIndex] = permu[i];
            else
                result[permu.length - vIndex + i] = permu[i];
        return result;
    }
    
    private static int[] transvere(int[] permu) {
        int[] result = new int[permu.length];
        for (int i = 0; i < permu.length; i++)
            result[i] = permu[permu.length - 1 - i];
        return result;
    }
}
